队列经典应用场景——数据结构系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）

一、迷宫求解

  迷宫求解是 BFS 的经典实战场景，核心需求：从迷宫起点到终点，找到「最少步数」的路径（DFS 能找路径但无法保证最短，BFS 是最优解）。

  广度优先搜索（BFS）是队列的标志性应用，核心解决「层级遍历、最短路径」类问题，

问题描述：

• 迷宫表示：二维数组 maze[][]，0 表示可走，1 表示墙，start=(sx,sy) 起点，end=(ex,ey) 终点。

算法解析：

BFS 的「层级特性」天然适配「最短路径」—— 每一层对应「走了 n 步」，第一次到达终点时的层数就是最少步数：

1. 初始化队列，存入起点坐标 (sx,sy)，并标记起点已访问（避免重复走）；
2. 定义方向数组（上下左右）：dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}；
3. 循环处理队列：
   • 出队当前坐标，若当前坐标是终点 → 返回当前步数；
   • 遍历四个方向，计算新坐标；
   • 若新坐标「在迷宫范围内」且「可走」且「未访问」→ 标记已访问，入队新坐标，步数 + 1；
4. 队空则说明无路径。

#include <iostream>
#include"ArrayQueue.h"

using namespace std;

// 迷宫坐标结构体（存储x,y坐标+步数）
struct Pos{
    int x;
    int y;
    int step;
};

// 迷宫最短路径求解（BFS+队列）
// maze：迷宫数组，rows/cols：迷宫行列数，sx/sy：起点，ex/ey：终点
int mazeShortestPath(int maze[][5], int rows, int cols, int sx, int sy, int ex, int ey) {
    // 边界校验
    if (sx < 0 || sx >= rows || sy < 0 || sy >= cols ||
        ex < 0 || ex >= rows || ey < 0 || ey >= cols ||
        maze[sx][sy] == 1 || maze[ex][ey] == 1) {
        return -1; // 起点/终点非法
    }
    if (sx == ex && sy == ey) {
        return 0; // 起点即终点
    }

    ArrayQueue<Pos> queue;
    int visited[500][500] = {{0}}; // 标记是否访问过
    int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; // 上下左右

    // 起点入队
    queue.enQueue({sx, sy, 0});
    visited[sx][sy] = 1;

    while (!queue.isEmpty()) {
        Pos cur = queue.deQueue();

        // 遍历四个方向
        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dirs[i][0];
            int ny = cur.y + dirs[i][1];
            // 到达终点，返回步数+1
            if (nx == ex && ny == ey) {
                return cur.step + 1;
            }
            // 新坐标合法且可走、未访问
            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && maze[nx][ny] == 0 && !visited[nx][ny]) {
                visited[nx][ny] = 1;
                queue.enQueue({nx, ny, cur.step + 1});
            }
        }
    }
    return -1; // 无路径
}


// 测试案例
int main() {
    // 迷宫示例：5行5列，0可走，1墙
    int maze[5][5] = {
        {0, 1, 0, 0, 0},
        {0, 1, 0, 1, 0},
        {0, 0, 0, 1, 0},
        {1, 1, 0, 1, 0},
        {0, 0, 0, 0, 0}
    };
    int sx = 0, sy = 0; // 起点(0,0)
    int ex = 4, ey = 4; // 终点(4,4)
    int minStep = mazeShortestPath(maze, 5, 5, sx, sy, ex, ey);
    
    if (minStep == -1) {
        printf("迷宫无有效路径！\n");
    } else {
        printf("迷宫从(%d,%d)到(%d,%d)的最短步数：%d\n", sx, sy, ex, ey, minStep); // 预期：8
    }
    return 0;
}
        

输出结果

迷宫从(0,0)到(4,4)的最短步数：8
        

二、任务排队

队列是「任务调度、消息通信」的核心数据结构。

问题描述：

• 打印机任务排队：多个程序提交打印任务，打印机按「先提交先打印」的顺序处理；
• 消息队列（MQ）：分布式系统中，生产者发送消息到队列，消费者按顺序消费；
• 线程池任务队列：多个线程提交任务，线程池按顺序执行任务。

算法解析：

利用队列「先进先出」的特性，保证任务 / 消息按「提交顺序」处理，避免插队，核心逻辑：

1. 任务提交 → 入队；
2. 处理任务 → 出队队头任务，执行；
3. 队空则等待新任务，队满则拒绝新任务（或阻塞）。

#include <iostream>

using namespace std;

// 打印任务结构体
struct PrintTask{
    int taskId;     // 任务ID
    char content[50]; // 打印内容
};

// 模拟打印机任务队列
void printerQueueSim() {
    ArrayQueue<PrintTask> queue;
    // 提交3个打印任务
    PrintTask task1 = {1, "简历.pdf"};
    PrintTask task2 = {2, "论文.docx"};
    PrintTask task3 = {3, "报表.xlsx"};

    queue.enQueue(task1);
    queue.enQueue(task2);
    queue.enQueue(task3);

    printf("打印机开始处理任务（先进先出）：\n");
    while (!queue.isEmpty()) {
        PrintTask taskAddr;
        taskAddr = queue.deQueue();
        PrintTask *cur = &taskAddr;
        printf("处理任务%d：打印 %s\n", cur->taskId, cur->content);
    }
    printf("所有打印任务处理完成！\n");
}

// 测试案例
int main() {
    printerQueueSim();

    return 0;
}
        

输出结果

打印机开始处理任务（先进先出）：
处理任务1：打印 简历.pdf
处理任务2：打印 论文.docx
处理任务3：打印 报表.xlsx
所有打印任务处理完成！
            

三、滑动窗口

滑动窗口最大值：给你一个整数数组，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧，每向右滑动一次取窗口中最大值。

问题描述：

• 给定数组 [1,3,-1,-3,5,3,6,7]，窗口大小为 3，求每个窗口的最大值：[3,3,5,5,6,7]。
• 过程如下：
• [ 1 3 -1 ] -3 5 3 6 7 → 3
• 1 [ 3 -1 -3 ] 5 3 6 7 → 3
• 1 3 [ -1 -3 5 ] 3 6 7 → 5
• 1 3 -1 [ -3 5 3 ] 6 7 → 5
• 1 3 -1 -3 [ 5 3 6 ] 7 → 6
• 1 3 -1 -3 5 [ 3 6 7 ] → 7

算法解析：

维护一个「单调递减队列」，队列中存储数组下标，保证队头是当前窗口的最大值下标

1. 头出「超出窗口范围」的下标（窗口左边界 i-k+1）；
2. 尾出「小于当前元素」的下标；
3. 尾入当前下标；
4. 当遍历到 i ≥ k-1（窗口形成），队头下标对应的元素就是当前窗口的最大值。

#include <iostream>
#include <vector>
#include"LinkedDeque.h"

using namespace std;

// 滑动窗口最大值：双端队列解法
void maxSlidingWindow(int nums[], int n, int k) {
    vector<int> result;       // 存储每个窗口的最大值
    LinkedDeque<int> dq;       // 双端队列，存储nums的下标，而非值

    for (int i = 0; i < n; ++i) {
        // 1. 移除超出窗口范围的队头元素（窗口左边界：i - k + 1）
        while(!dq.isEmpty() && dq.getHead() < i - k + 1) {
            dq.popHead();
        }

        // 2. 移除队列尾部所有小于当前元素的下标（维护递减队列）
        while(!dq.isEmpty() && nums[dq.getTail()] < nums[i]) {
            dq.popTail();
        }

        // 3. 将当前元素下标加入队列尾部
        dq.pushTail(i);

        // 4. 当遍历到第k-1个元素后，开始记录每个窗口的最大值
        if (i >= k - 1) {
            result.push_back(nums[dq.getHead()]);
        }
    }

    // 输出结果：3 3 5 5 6 7
    cout << "滑动窗口最大值结果：";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
}


// 测试案例
int main() {
    int nums[] = {1,3,-1,-3,5,3,6,7};
    int n = sizeof(nums)/sizeof(nums[0]);
    int k = 3;
    maxSlidingWindow(nums, n, k); // 输出：3 3 5 5 6 7

    return 0;
}
        

输出结果

滑动窗口最大值结果：3 3 5 5 6 7
            

#include <iostream>
#include <vector>
#include"LinkedDeque.h"

using namespace std;

// 滑动窗口最小值：双端队列解法
void minSlidingWindow(int nums[], int n, int k) {
    vector result;       // 存储每个窗口的最小值
    LinkedDeque dq;       // 双端队列，存储nums的下标，而非值

    for (int i = 0; i < n; ++i) {
        // 1. 移除超出窗口范围的队头元素（窗口左边界：i - k + 1）
        while(!dq.isEmpty() && dq.getHead() < i - k + 1) {
            dq.popHead();
        }

        // 2. 移除队列尾部所有大于当前元素的下标（维护递减队列）
        while(!dq.isEmpty() && nums[dq.getTail()] > nums[i]) {
            dq.popTail();
        }

        // 3. 将当前元素下标加入队列尾部
        dq.pushTail(i);

        // 4. 当遍历到第k-1个元素后，开始记录每个窗口的最小值
        if (i >= k - 1) {
            result.push_back(nums[dq.getHead()]);
        }
    }

    // 输出结果：3 3 5 5 6 7
    cout << "滑动窗口最小值结果：";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
}


// 测试案例
int main() {
    int nums[] = {1,3,-1,-3,5,3,6,7};
    int n = sizeof(nums)/sizeof(nums[0]);
    int k = 3;
    minSlidingWindow(nums, n, k); // 输出：-1 -3 -3 -3 3 3

    return 0;
}
        

输出结果

滑动窗口最小值结果：-1 -3 -3 -3 3 3
            

四、约瑟夫环

约瑟夫环是经典的循环队列问题：n 个人围成一圈，从第 1 个人开始报数，报到 m 的人出列，接着下一个人继续报数，直到最后只剩 1 个人，求最后存活的人的编号。

问题描述：

• 例如：n=5 人（编号 1-5），m=3（数到 3 出列）：
  1. 初始圈：1 → 2 → 3 → 4 → 5
  2. 第 1 轮：数到 3，3 出列 → 圈：4 → 5 → 1 → 2
  3. 第 2 轮：从 4 开始数，数到 1（4→5→1），1 出列 → 圈：2 → 4 → 5
  4. 第 3 轮：从 2 开始数，数到 5（2→4→5），5 出列 → 圈：2 → 4
  5. 第 4 轮：从 2 开始数，数到 2（2→4→2），2 出列 → 最后剩 4

算法解析：

利用队列的「循环特性」模拟报数过程：

• 1~n 依次入队；
• 循环报数：
  • 队头元素出队，若报数未到 m → 重新入队（模拟绕圈）；
  • 若报数到 m → 该元素出列（不再入队）；
• 队中仅剩 1 个元素时，就是存活的人。

#include <iostream>
#include"ArrayQueue.h"

using namespace std;

// 约瑟夫环问题（队列模拟）
int josephus(int n, int m) {
    if (n <= 0 || m <= 0) return -1;
    ArrayQueue<int> queue;
    // 1~n入队
    for (int i = 1; i <= n; i++) {
        queue.enQueue(i);
    }

    int count = 0; // 报数计数器
    while (queue.getSize() > 1) {
        int val = queue.deQueue();// 队头出队
        count++;
        // 报数未到m，重新入队
        if (count != m) {
            queue.enQueue(val);
        } else {
            count = 0; // 重置计数器
            printf("出列的人：%d\n", val);
        }
    }
    // 队中剩余的最后一个元素
    int survivor = queue.getHead();

    return survivor;
}

// 测试案例
int main() {
    int n = 5, m = 3; // 5人报数，报到3出列
    int survivor = josephus(n, m);
    printf("约瑟夫环（n=%d,m=%d）最后存活的人：%d\n", n, m, survivor); // 预期：4

    return 0;
}
        

输出结果

出列的人：3
出列的人：1
出列的人：5
出列的人：2
约瑟夫环（n=5,m=3）最后存活的人：4
            

五、总结

1. 队列是算法的核心基石，BFS、任务调度、最短路径等核心场景都依赖队列的「先进先出」特性，本文的 4 个场景是队列的高频应用，优先级排序：
2. 迷宫最短路径 > 任务排队 > 滑动窗口最大值 > 约瑟夫环
3. 滑动窗口最大值采用双端队伍实现，其它场景的代码都基于同一个循环队列封装，学会队列的基础操作后，所有应用场景都是「换汤不换药」，掌握「先进先出」的核心规律，队列的所有题目都能轻松解决！在学习二叉树数据结构时，我们还会学习使用队列实现BFS（二叉树层序遍历）